package algocasts;

import java.util.Stack;

public class P14_isPalindromeList {
    class ListNode {
        int val;
        ListNode next;
    }

    public boolean isPalindromeList_Stack(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        for (ListNode p = head; p != null; p = p.next)
            stack.push(p.val);
        for (ListNode p = head; p != null; p = p.next)
            if (stack.pop() != p.val) return false;
        return true;
    }

    public boolean isPalindromeList_ReverseList(ListNode head) {
        int len = 0;
        for (ListNode p = head; p != null; p = p.next, len++) ;

        ListNode cur = head, pre = null;
        for (int i = 0; i < len / 2; i++) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        if (len % 2 == 1) cur = cur.next;
        for (; pre != null && cur != null; pre = pre.next, cur = cur.next)
            if (pre.val != cur.val) return false;
        return true;
    }

}
